class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        vector<int> dp(n + 1, 0);
        int result = 0;
        for (int i = 2; i <= n; i++) {
            if (s[i - 1] == '(') dp[i] = 0;
            else {
                if (s[i - 2] == '(') {
                    dp[i] = dp[i - 2] + 2;
                }
                else {
                    if (i - dp[i - 1] - 2 >= 0 && s[i - dp[i - 1] -2] == '(') {
                        dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;
                    }
                    else {
                        dp[i] = 0;
                    }
                }
            }
            result = max(result, dp[i]);
        }
        return result;
    }
};
